import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by forcht on 2018/5/21.
 */
public class Solution {
    ArrayList<ArrayList<Integer>> list=new ArrayList<>();
    ArrayList<Integer> curList=new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        boolean[] flag=new boolean[num.length];
        Arrays.sort(num);
        dfs(num,flag);
        return list;
    }

    public void dfs(int[] num,boolean[] flag){
        if (curList.size()==num.length){
            list.add((ArrayList<Integer>) curList.clone());
            return;
        }
        Integer t=null;
        for(int i=0;i<num.length;i++){
            if (t!=null&&i>0&&num[i]==t)continue;
            if (!flag[i]){
                curList.add(num[i]);
                flag[i]=true;
                dfs(num,flag);
                curList.remove(curList.size()-1);
                flag[i]=false;
                t=num[i];
            }
        }
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        int[] a={1,1,2,2};
        System.out.println(solution.permuteUnique(a));
    }
}
